我们从最小值的理论存在性，过渡到优化的算法引擎。我们的核心目标是 最小化 $f(x)$ (9.1) 其中 $f: \mathbf{R}^n \to \mathbf{R}$ 是凸函数且二阶连续可微。由于 $f$ 可微且凸，点 $x^*$ 为最优的充要条件是 $\nabla f(x^*) = 0$。
算法框架
数值解法构建一个 最小化序列：一系列点 $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$，满足当 $k \to \infty$ 时 $f(x^{(k)}) \to p^*$。每一步通过 $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$ 更新位置，其中 $\Delta x$ 为下降方向。
初始化与收敛性
本章描述的方法需要一个合适的初始点 $x^{(0)}$。该初始点必须位于 $\text{dom } f$ 中，此外子水平集 $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ 必须是闭集。这确保了序列始终处于一个行为良好的区域，此时 Hessian 矩阵能提供有用信息。
下降方向
最简单的方向是 $\Delta x = -\nabla f(x)$。然而，效率通常需要通过以下方式考虑不同几何结构： 最速下降方向：
- 二次范数： $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$。
- $L_\infty$ 范数： $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ （坐标下降法）。
二阶模型与信赖域
牛顿法使用二阶泰勒近似： $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ 当 $v = \Delta x_{nt}$（牛顿步）时，该二次函数取得最小值。我们定义一个 信赖域：集合 $\{v \mid \|v\|_2 \le \gamma\}$。参数 $\gamma$ 反映了我们对二阶模型的信心。当模型准确时，我们通过以下方式求解方向 $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ 在 KKT 系统中求解。
🎯 收敛性核心原则
效率通过误差 $f(x^{(k)}) - p^*$ 消失的速度来衡量。对于强凸函数， 误差 $f(x^{(k)}) - p^*$ 收敛至零的速度至少与几何级数一样快。在迭代数值方法的背景下，这称为线性收敛。
- 次优性界： $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$，当 $\lambda(x) < 1$ 时成立。
- 自共轭和： 若 $f_1, f_2$ 为自共轭函数，则 $f_1 + f_2$ 也是自共轭函数。
- Hessian 稀疏性： 若满足以下条件，则可提高效率： Hessian 带状结构条件：$\nabla^2 f(x)_{ij} = 0$，当 $|i-j| > k$ 时成立 成立。